package J20241204_Partition;
import java.util.*;
/**
 * Created with IntelliJ IDEA.
 * Description: 分治——计算右侧小于当前元素的个数
 * User: 王圆豪
 * Date: 2024-12-04
 * Time: 21:48
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.countSmaller(new int[]{-1,-1}).toString());
    }
    int[] ret;
    int[] pos;
    public List<Integer> countSmaller(int[] nums) {
        ret = new int[nums.length];
        pos = new int[nums.length];
        for(int i = 0; i < nums.length; i++){
            pos[i] = i;
        }
        findSmaller(nums, 0, nums.length-1);
        List<Integer> p = new ArrayList<>();
        for(int i = 0; i < nums.length; i++){
            p.add(ret[i]);
        }
        return p;
    }

    public void findSmaller(int[] nums, int l, int r){
        if(l >= r) return;

        int mid = (l+r)/2;
        findSmaller(nums, l, mid);
        findSmaller(nums, mid+1, r);

        int left = l, right = mid+1, sz = 0, sz2 = 0;
        int[] tmp = new int[r-l+1];
        int[] tmp2 = new int[r-l+1];
        while(left <= mid && right <= r){
            if(nums[left] <= nums[right]){
                tmp[sz++] = nums[right];
                tmp2[sz2++] = pos[right++];
            }else{
                tmp[sz++] = nums[left];
                tmp2[sz2++] = pos[left];
                ret[pos[left]] += (r - right + 1);
                left++;
            }
        }
        while(left <= mid) {tmp[sz++] = nums[left];tmp2[sz2++] = pos[left++];}
        while(right <= r) {tmp[sz++] = nums[right];tmp2[sz2++] = pos[right++];}

        for(int i = l; i <= r; i++){
            nums[i] = tmp[i-l];
            pos[i] = tmp2[i-l];
        }
    }
}
